Directing attention to FIG. 1, the IEEE 1394a standard defines communication protocols between nodes 10 on a computer network 12. Nodes 10 can be personal computers, workstations, or other computing devices. Each node has a PHY 14, which facilitates communication between the nodes and other nodes in network 12. PHY 14 has a plurality of ports so that multiple connections can be made to node 10. Nodes 10 can be connected by cable 16, or other suitable communication medium, to implement computer network 12. It is one of the goals of the 1394a standard to implement a protocol that treats all communication media connecting nodes 10 collectively as bus 16. To achieve this objective, two processes are executed on each of the nodes: a tree_ID process and a self_ID process.
The tree_ID process is executed in a distributed manner among the nodes to configure a tree structure among nodes 10. The tree_ID process executed on each node establishes a hierarchy among nodes 10 such that each connection between two nodes 10 defines one node as the parent of the other node and the other node as the child of the first node. A node 10 may thus be parent to zero or more children, and each node 10 has at most one parent. On each node 10, a flag on each port in PHY 14 indicates the peer node as either a parent or a child. A root node 10-1 eventually is determined to be a node that has only children and no parent. By establishing a hierarchy among nodes 10, the communication protocols of the 1394a standard are able to function properly. The root node has particular responsibilities, such as acting as cycle master and issuing cycle start packets. This function is essential to isochronous operation, which, in turn, is essential to the use of the 1394 standard in consumer digital audio-visual applications among others. When a node has identified all connections to its PHY 14 as being connections to children with the exception of one connection, it is assumed that the remaining, unidentified connection points to a potential parent node.
Once all of nodes 10 have completed the tree_ID process, and every node has set its flags on all its ports to either parent or child, the network configuration state moves to the self_ID process. The self_ID process takes place in a distributed manner. The 1394a standard specifies that each child node must wait for a signal from its parent node before beginning its contribution to the self_ID process, and that the root node 10-1 initiates the process. As defined in the 1394a standard, six bits are provided on each node to designate a unique identifier within network 12. A maximum value, 63, is reserved as a broadcast identifier for all nodes in network 12. Thus, if a node needs to send a message to all nodes 10, it sets the address message for node 63 and all nodes in network 12 receive this message. Node value 63 is not individually addressable. A node having a value of 63 indicates a malconfigured bus. Any such node may repeat packets originated by other nodes, but is not permitted otherwise to participate in bus activity. The remaining identifiers, 0 through 62, are available for identification designation.
During the self_ID process, each node 10 in turn assigns itself a unique identifier, so that the process assigns a unique identifier to nodes 10 on network 12. Each node 10 maintains a register that records the next available identifier. When a node 10 receives a notification that another node 10 has assigned itself an identifier, the node 10 updates its register to the next value incrementally. However, the value in the register is not allowed to exceed 63. When a child node is instructed by its parent node to execute its contribution to the self_ID process, the child first instructs its children (if any) in turn to execute their contributions to the self_ID process. When all its children have completed their contributions, the node checks its internal register for the next available value and selects this value as its identifier. It then broadcasts this value across network 12 and all nodes update their identification registers with this node-value assignment. The child node then instructs the parent node that it has completed the self_ID process. Once all of the children of a parent node have assigned values to themselves, the parent node selects a value in a similar fashion, and sends a message to its parent that it has finished. This process continues up the tree until root node makes the final node-value assignment. The root thus always assigns itself the highest node-value. This self_ID process as executed in a tree structure is illustrated in FIG. 2.
The self_ID process works smoothly as long as there are 62 or less nodes connected in network 10. In these cases, the root will have a node value of 62 or less. If more than 63 nodes are present on the bus, then the nodes after the 63rd to allocate themselves identifiers, including the root node, are all allocated Physical_ID 63. FIG. 3 illustrates a network where more than 63 nodes are connected and an attempt to execute self_ID has failed. As shown, node 20 is a non-root node that has selected the value of 62 for itself, thus denying the root node the opportunity to allocate itself a value of 62 or less. Because the 1394a standard defines special functions for the root node, the network illustrated in FIG. 3 has failed to properly execute the self_ID process and communication cannot proceed properly. There is a need for a solution to this problem that allows a network to be configured in a fault tolerant manner that accommodates the 1394a standard and thus realizes its benefits.